New results on EX graphs

Title: New results on EX graphs
Creator: Tang, Jianmin; Lin, Yuqing; Miller, Mirka
Relation: Mathematics in Computer Science Vol. 3, Issue 1, p. 119-126
Publisher Link: http://dx.doi.org/10.1007/s11786-009-0009-6
Publisher: Birkhauser
Resource Type: journal article
Date: 2010
Description: By the extremal number ex(n; t) = ex(n; {C₃,C₄, . . . ,Cᵼ }) we denote the maximum size (that is, number of edges) in a graph of order n > t and girth at least g ≥ t + 1. The set of all the graphs of order n, containing no cycles of length ≤ t, and of size ex(n; t), is denoted by EX(n; t) = EX(n; {C₃,C₄, . . . ,Cᵼ }), these graphs are called EX graphs. In 1975, Erdős proposed the problem of determining the extremal numbers ex(n; 4) of a graph of order n and girth at least 5. In this paper, we consider a generalized version of this problem, for t ≥ 5. In particular, we prove that ex(29; 6) = 45, also we improve some lower bounds and upper bounds of exᴜ(n; t), for some particular values of n and t.
Subject: EX graph; extremal number; cages; Erdős
Identifier: http://hdl.handle.net/1959.13/932199
Identifier: uon:11283
Identifier: ISSN:1661-8270
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format